One challenge in the design of computer games is agent movement—the motion of an entity or object through its environment. Pathfinding strategies have the task of finding a path from any coordinate in a game world to any other (possible) coordinate under a given set of constraints. Pathfinding systems take as input a starting point, a destination point, knowledge of its environment (e.g., where obstacles are located), and information regarding the agent if relevant; they then find a series of points that constitute one or more paths the agent can follow to navigate from its starting point to its destination point.
A game's world geometry is often stored in a structure referred to as a “map” and usually contains all of the polygons that make up the game's environment. To reduce the amount of computation required, a game's map is often simplified. The pathfinder uses these simplified representations to determine a path from start to end. The most common forms of simplified representations are navigation meshes and waypoints. A navigation mesh is a set of convex polygons that describe the walkable surface of a three-dimensional (3D) environment. Waypoints are a collection of nodes with links between them. Waypoints are useful for creating efficient obstacle free paths through static maps but are generally unable to deal with dynamic worlds.